package zifuchuan.zifuchuanpipei;

public class _01RabinKarp {
    /**
     * 滚动hash法
     * 对目标字符串按d进制求值,mod h 取余作为其hash
     * 对源串,依次求出m个字符的hash,保存在数组中(滚动计算)
     * 匹配时,只需比对目标串的hash值和预存的源串的hash值表
     */
    final static long seed = 31;

    public static void main(String[] args) {
        String s = "ABABABA";
        String p = "ABA";
        match(p, s);
    }

    public static void match(String p, String s) {
        long hash_p = hash(p);//p的hash值
        int p_len = p.length();
        for (int i = 0; i+ p_len <= s.length(); i++) {
            long hash_i = hash(s.substring(i,i+ p_len));//i起点,长度为plen的子串的hash值
            if (hash_i==hash_p){
                System.out.println("match:"+i);
            }
        }
    }

    static long hash(String str) {
        long h = 0;
        for (int i = 0; i != str.length(); ++i) {
            h = seed * h + str.charAt(i);
        }
        return h % Long.MAX_VALUE;
    }
}
